package com.xy.algorithm;

import java.util.Arrays;

public class HeapSort {

    /**
     *冒泡排序：
     * 说明：a,b分别代表列表的两端，共n个元素
     * 1.从a端开始，相邻的两个元素依次比较，前一个元素比后一个元素大，交换位置
     * 2.遍历一次后，最大的元素到达b端
     * 3.然后从n-1个元素进行步骤一
     * @param li 无序队列
     */
    public static void bubbleSort(int[] li) {

    }

    /**
     * 选择排序:
     *1.遍历比较一次，得到一个最大的数
     *2.把最大的数与第一个数交换
     *3.然后重复1步骤
     *4.把最大的数与有序区的最后一个数交换
     * @param li
     */
    public static void selectSort(int[] li) {

    }

    /**
     * 插入排序：
     *
     * @param li
     */
    public static void insertSort(int[] li) {

    }


    /**
     * 快速排序：
     * 1.随机第一个元素,把比第一个元素小的依次排在左边,大的排在右边
     * 1.1.与右侧游标中的值比较,如果比元素大不动,移动右侧游标
     * 1.2.如果小,把值存到左侧,移动左侧游标
     * 1.3.然后从左开始
     * 2.然后把左右两边的队列重复步骤1
     * @param li
     */
    public static void quickSort(int[] li, int left, int right) {

    }
    private static int partition(int[] li, int left, int right) {
        return 0;
    }

    /**
     * 堆排序：
     * 1.构建堆
     * @param li 列表
     * @param low 堆的根节点位置
     * @param high 堆的最后一个元素的位置
     */
    private static void sift(int[] li, int low, int high) {
        int i = low;
        int j = low * 2 + 1;
        int tmp = li[low];
        while (j < high) {
            while (j + 1 < high && li[j + 1] > li[j]) {
                j++;
            }
            if (tmp < li[j]) {
                li[i] = li[j];
                i = j;
                j = i * 2 + 1;
            } else {
                break;
            }
        }
        li[i] = tmp;
    }
    public static void heapSort(int[] li, int n) {
        for (int i = (n -1) / 2; i > -1; i--) {
            sift(li, i, n);
        }
        for (int j = n; j > -1; j--) {
            int tmp = li[0];
            li[0] = li[j];
            li[j] = tmp;
            sift(li, 0, j - 1);
        }
    }
    public static void main(String[] args) {
        int[] li = { 5, 7, 4, 6, 3, 1, 2, 9, 8 };
//        int[] li = new int[1000000];
//        Random random = new Random();
//        for (int i = 0 ; i < 1000000; i++) {
//            li[i] = random.nextInt(1000000);
//        }

        long startTime = System.currentTimeMillis();
//        bubbleSort(li);
//        selectSort(li);
//        insertSort(li);
        heapSort(li, li.length -1);
//        heapSort(li, li.length);
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
        Arrays.stream(li).forEach(i -> System.out.print(i + " "));
        System.out.println();
        System.out.println(li.length);
    }
}
